#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "FT_generalization.h"

#include "SpecialTerm.h"


List<FeatureTerm> *DGeneralization(FeatureTerm *base,Ontology *ontology,FTKBase *domain_model)
{
	List<FeatureTerm> l_domain,l_feature,l_sort,l_path,l_set,l_special,*l=new List<FeatureTerm>;
	List<FeatureTerm> *nodes,ltmp;
	FeatureTerm *node,*node2,*modified_node,*ft;
	List< List<Path> > *paths;
	List< List<Sort> > *mg_sorts;
	List<Path> *pathl;
	List<Sort> *mg_sortl;
	Sort *mg_sort,*sort;
	Path *path;
	bool is_domain_object;
	List< FeatureTerm > already_considered_for_path_equalty;

	base->Allnodes(&nodes,ontology,domain_model);
//	printf("this FT has %i nodes\n",nodes->Length());
	
	nodes->Rewind();
	while(nodes->Iterate(node)) {
		is_domain_object=false;
		if (domain_model!=0 && domain_model->MemberP(node)) is_domain_object=true;
/*
		{
			char *s;
			s=node->toNiceString();
			printf("Considering node (%s): %s\n",(is_domain_object ? "true":"false"),s);
			delete []s;
		}
*/
		/* Domain generalizations: */ 
		if (is_domain_object || 
			(node->isFloat() && node->hasValue()) || 
			(node->isInt() && node->hasValue()) || 
			(node->isSymbol() && node->hasValue())) {
			ft=base->clone_keepingTrackOfNode(node,&modified_node,domain_model);
			if (modified_node!=0) {
				node2=new FeatureTerm((Symbol *)0,modified_node->getSort(),0);
				modified_node->assign(node2);				
				delete node2;
				l_domain.Add(ft);
/*
				{
					char *s;
					s=node->toNiceString();
					printf("DOMAIN: %s -> %s\n",s,modified_node->getSort()->get());
					delete []s;
				} 
*/
			} else {
				delete ft;
			} /* if */ 			
		} /* if */ 

		/* Path equalty eliminations: */ 
		if (!is_domain_object) {
			List<FeatureTerm> l,ltmp;
			bool valid=true;

			already_considered_for_path_equalty.Rewind();
			while(already_considered_for_path_equalty.Iterate(ft)) {
				if (ft->same(node)) valid=false;
			} /* while */ 

			if (valid) {
				l.Instance(*nodes);
				l.Rewind();
				while(l.Iterate(ft)) {
					if (ft->same(node)) {
						ltmp.Add(ft);
					} /* if */ 
				} /* while */ 

//				printf("%i copies of this node\n",ltmp.Length());

				if (ltmp.Length()<=2) ltmp.ExtractIni();	/* the first element is extracted, to avoid generating duplicated terms */ 
				while(!ltmp.EmptyP()) {
					node2=ltmp.ExtractIni();
					ft=base->clone_keepingTrackOfNode(node2,&modified_node,domain_model);
					if (modified_node!=0) {
						node2=modified_node->clone(domain_model);
						modified_node->assign(node2);
						delete node2;
						l_path.Add(ft);
					} else {
						char *s;
						s=node2->toStringNOOS(domain_model);
						printf("Node: %s lost during cloning...\n",s);
						delete []s;
					} /* if */ 
				} /* if */ 
				already_considered_for_path_equalty.Add(node);
			} /* if */ 

		} /* if */ 


		// Special generalizations:
		if (node->isSpecial()) {
			List<FeatureTerm> *ltmp;
			FeatureTerm *value;

			ltmp=node->getSpecialTerm()->DGeneralization(ontology,domain_model);

			if (ltmp!=0) {
				while(!ltmp->EmptyP()) {
					value=ltmp->ExtractIni();
					ft=base->clone_substituting(node,value,domain_model);
					l_special.Add(ft);
					delete value;
				} // while 
				delete ltmp;
			} // if 
		} // if 
	} /* while */ 

	while(!already_considered_for_path_equalty.EmptyP()) already_considered_for_path_equalty.ExtractIni();
	while(!nodes->EmptyP()) nodes->ExtractIni();
	delete nodes;

//	printf("Second stage:\n");

	base->nodesAllPathsSorts(&nodes,&paths,&mg_sorts,ontology);

	nodes->Rewind();
	paths->Rewind();
	mg_sorts->Rewind();
	while(nodes->Iterate(node) &&
		  paths->Iterate(pathl) &&
		  mg_sorts->Iterate(mg_sortl)) {

		path=pathl->operator [](0);
		mg_sort=mg_sortl->operator [](0);

		is_domain_object=false;
		if (domain_model!=0 && domain_model->MemberP(node)) is_domain_object=true;
/*
		{
			char *s;
			s=node->toNiceString();
			printf("Considering node (%s): %s\n",(is_domain_object ? "true":"false"),s);
			delete []s;
		}
*/
		if (!is_domain_object) {
			/* Set reduction: */ 
			if (node->isSet()) {
				if (node->set_values_quick()->Length()>2) {
					List<FeatureTerm> l;
					FeatureTerm *ft2;
					int i;

//					printf("Reducing a set of size %i\n",node->set_values_quick()->Length());

					l.Instance(*node->set_values_quick());
					l.Rewind();
					i=0;
					while(l.Iterate(ft)) {
						if (ft->leafP() && ft->getSort()==mg_sort && (domain_model==0 || !domain_model->MemberP(ft))) {
							ft=base->clone_keepingTrackOfNode(node,&modified_node,domain_model);
							ft2=modified_node->set_values_quick()->operator [](i);
							modified_node->removeSetValue(ft2);
							l_set.Add(ft);
						} /* if */ 
						i++;
					} /* while */ 
				} else if (node->set_values_quick()->Length()==2) {
					FeatureTerm *ft2;

//					printf("Reducing a set of size %i\n",node->set_values_quick()->Length());

					ft=node->set_values_quick()->operator [](0);
					if (ft->leafP() && ft->getSort()==mg_sort && (domain_model==0 || !domain_model->MemberP(ft))) {
						ft=base->clone_keepingTrackOfNode(node,&modified_node,domain_model);
						ft2=new FeatureTerm(modified_node->set_values_quick()->operator [](1));
						modified_node->assign(ft2);
						delete ft2;	
						l_set.Add(ft);
					} /* if */ 

					ft=node->set_values_quick()->operator [](1);
					if (ft->leafP() && ft->getSort()==mg_sort && (domain_model==0 || !domain_model->MemberP(ft))) {
						ft=base->clone_keepingTrackOfNode(node,&modified_node,domain_model);
						ft2=new FeatureTerm(modified_node->set_values_quick()->operator [](0));
						modified_node->assign(ft2);
						delete ft2;	
						l_set.Add(ft);
					} /* if */ 
				} else {
					printf("Warning: set of less than size 2 detected!\n");
				} /* if */ 
			} /* if */ 

			/* Sort generalization: */ 
			if (node->isAbstract() ||
				node->isFeatureTerm() ||
				(node->isInt() && !node->hasValue()) ||
				(node->isFloat() && !node->hasValue()) ||
				(node->isSymbol() && !node->hasValue())) {
				List<Symbol> *fn;
				Symbol *f;
				Sort *super;
				bool can_be_generalized=true;

				sort=node->getSort();
				super=sort->getSuper();

				if (super!=0 && mg_sort->isSubsort(super)) {
					fn=sort->getFeatures();

					fn->Rewind();
					while(fn->Iterate(f) && can_be_generalized) {
						ft=node->featureValueQuick(f);
						if (ft!=0 && !super->hasFeature(f)) can_be_generalized=false;
					} /* while */ 
					delete fn;

					if (can_be_generalized) {
						ft=base->clone_keepingTrackOfNode(node,&modified_node,domain_model);
						if (modified_node!=0) {
							modified_node->setSort(super);
							l_sort.Add(ft);

//							printf("SORT: %s -> %s\n",sort->get(),super->get());
						} else {
							delete ft;
						} /* if */ 			
					} /* if */ 
					
				} /* if */ 
			} /* if */ 


			/* Feature elimination: */ 
			if (node->isFeatureTerm()) {
				List<Symbol> *fn;
				Symbol *f;

				sort=node->getSort();
				fn=sort->getFeatures();

				fn->Rewind();
				while(fn->Iterate(f)) {
					ft=node->featureValueQuick(f);
					if (ft!=0 && (domain_model==0 || !domain_model->MemberP(ft))) {
						if (ft->leafP() && ft->getSort()==sort->featureSort(f)) {
							ft=base->clone_keepingTrackOfNode(node,&modified_node,domain_model);
							if (modified_node!=0) {
								modified_node->removeFeatureValue(f);
								l_feature.Add(ft);
							} else {
								delete ft;
							} /* if */ 
						} /* if */ 
					} /* if */ 
				} /* while */ 
				delete fn;

			} /* if */ 
		} /* if */ 

	} /* while */ 

	while(!nodes->EmptyP()) nodes->ExtractIni();
	delete nodes;
	delete paths;
	while(!mg_sorts->EmptyP()) {
		mg_sortl=mg_sorts->ExtractIni();
		while(!mg_sortl->EmptyP()) mg_sortl->ExtractIni();
		delete mg_sortl;
	} /* while */ 
	delete mg_sorts;

//	printf("Generalizations: %i + %i + %i + %i + %i + %i= ",l_sort.Length(),l_path.Length(),l_feature.Length(),l_set.Length(),l_domain.Length(),l_special.Length());

	/* This is done to keep ordered the generalizations: SORT -> FEATURES -> SET -> PATH -> DOMAIN -> SPECIAL*/ 
	while(!l_sort.EmptyP()) l->Add(l_sort.ExtractIni());
	while(!l_feature.EmptyP()) l->Add(l_feature.ExtractIni());
	while(!l_set.EmptyP()) l->Add(l_set.ExtractIni());
	while(!l_path.EmptyP()) l->Add(l_path.ExtractIni());
	while(!l_domain.EmptyP()) l->Add(l_domain.ExtractIni());
	while(!l_special.EmptyP()) l->Add(l_special.ExtractIni());

//	printf("%i\n",l->Length());

	return l;
} /* DGeneralization */ 



void Generalize(FeatureTerm *base,List<FeatureTerm> *objects,List<FeatureTerm> *result,Ontology *ontology,FTKBase *domain_model,bool fast)
{
	List<FeatureTerm> l,todelete,to_process;
	List<FeatureTerm> *succesors;
	FeatureTerm *node,*succesor,*object,*ft;
	bool valid,does_not_advance;

	to_process.Add(base->cloneUnnamed(domain_model));
	while(!to_process.EmptyP()) {
		node=to_process.ExtractIni();

		l.Add(node);

		{
			char *s;

			s=node->toStringNOOS(domain_model);
			printf("------------------------------------------------------ (%i,%i)\n",l.Length(),to_process.Length());
			printf("Current node:\n%s\n",s);
			delete []s;
		}

		succesors=DGeneralization(node,ontology,domain_model);
		printf("%i succesors\n",succesors->Length());

		while(!succesors->EmptyP()) {
			succesor=succesors->ExtractIni();
/*
			{
				char *s;
				s=succesor->toStringNOOS(domain_model);
				printf("------------------------------\n");
				printf("Considering:\n%s\n",s);
				delete []s;
			}
*/
			valid=true;
			does_not_advance=false;

			if (objects!=0) {
				objects->Rewind();
				while(valid && objects->Iterate(object)) {
					if (!object->subsumes(succesor)) valid=false;
				} /* while */ 
			} /* if */ 

			if (valid) {
				
				/* Prune "l" and "to_process" lists: */ 
				l.Rewind();
				while(!does_not_advance && l.Iterate(ft)) {
					if (ft->subsumes(succesor)) {
						printf("does not advance 1\n");
						does_not_advance=true;
					} else {
						if (succesor->subsumes(ft)) {
							todelete.Add(ft);
						} /* if */ 
					} /* if */ 
				} /* while */ 
				while(!todelete.EmptyP()) {
					ft=todelete.ExtractIni();
					l.DeleteElement(ft);
					delete ft;
				} /* while */ 

				to_process.Rewind();
				while(!does_not_advance && to_process.Iterate(ft)) {
					if (ft->subsumes(succesor)) {
						printf("does not advance 2\n");
						does_not_advance=true;
					} else {
						if (succesor->subsumes(ft)) {
							todelete.Add(ft);
						} /* if */ 
					} /* if */ 
				} /* while */ 
				while(!todelete.EmptyP()) {
					ft=todelete.ExtractIni();
					to_process.DeleteElement(ft);
					delete ft;
				} /* while */ 

				if (!does_not_advance) {
					if (fast) succesors->Delete();
					to_process.Add(succesor);
				} else {
					delete succesor;
				} /* if */ 
			} else {
				delete succesor;
			} /* if */ 
		} /* while */ 
	} /* while */ 

	while(!l.EmptyP()) result->Add(l.ExtractIni());
} /* Generalize */ 



void Generalize(FeatureTerm *base,List<FeatureTerm> *objects,List<FeatureTerm> *result,List<int> *result_step,Ontology *ontology,FTKBase *domain_model,bool fast)
{
	List<FeatureTerm> l,todelete,to_process;
	List<int> l_step,to_process_step;
	int *step;
	List<FeatureTerm> *succesors;
	FeatureTerm *node,*succesor,*object,*ft;
	bool valid,does_not_advance;
	int i;

	to_process.Add(base->cloneUnnamed(domain_model));
	to_process_step.Add(new int(0));
	while(!to_process.EmptyP()) {
		node=to_process.ExtractIni();
		step=to_process_step.ExtractIni();

		l.Add(node);
		l_step.Add(new int(*step));
/*
		{
			char *s;

			s=node->toStringNOOS(domain_model);
			printf("------------------------------------------------------ (%i,%i)\n",l.Length(),to_process.Length());
			printf("Current node: (%i) \n%s\n",*step,s);
			delete []s;
		}
*/
		succesors=DGeneralization(node,ontology,domain_model);
//		printf("%i succesors\n",succesors->Length());

		while(!succesors->EmptyP()) {
			succesor=succesors->ExtractIni();
//			printf("*");
/*
			{
				char *s;
				s=succesor->toStringNOOS(domain_model);
				printf("------------------------------\n");
				printf("Considering:\n%s\n",s);
				delete []s;
			}
*/
			valid=true;
			does_not_advance=false;

			if (objects!=0) {
				objects->Rewind();
				while(valid && objects->Iterate(object)) {
					if (!object->subsumes(succesor)) {
//						printf("Generalization Warning!\n");
						valid=false;
					} // if 
				} /* while */ 
			} /* if */ 

			if (valid) {
				
				if (fast) {
					succesors->Delete();
					l.Delete();
					l_step.Delete();
					to_process.Add(succesor);
					to_process_step.Add(new int((*step)+1));
				} else {
					/* Prune "l" and "to_process" lists: */ 
					l.Rewind();
					while(!does_not_advance && l.Iterate(ft)) {
						if (ft->subsumes(succesor)) {
//							printf("does not advance 1\n");
							does_not_advance=true;
						} else {
							if (succesor->subsumes(ft)) {
								todelete.Add(ft);
							} /* if */ 
						} /* if */ 
					} /* while */ 
					while(!todelete.EmptyP()) {
						ft=todelete.ExtractIni();
						i=l.PositionRef(ft);
						l.DeleteElement(ft);
						delete ft;
						if (i>=0) l_step.DeletePosition(i);
					} /* while */ 

					to_process.Rewind();
					while(!does_not_advance && to_process.Iterate(ft)) {
						if (ft->subsumes(succesor)) {
//							printf("does not advance 2\n");
							does_not_advance=true;
						} else {
							if (succesor->subsumes(ft)) {
								todelete.Add(ft);
							} /* if */ 
						} /* if */ 
					} /* while */ 
					while(!todelete.EmptyP()) {
						ft=todelete.ExtractIni();
						i=to_process.PositionRef(ft);
						to_process.DeleteElement(ft);
						delete ft;
						if (i>=0) to_process_step.DeletePosition(i);
					} /* while */ 

					if (!does_not_advance) {
						to_process.Add(succesor);
						to_process_step.Add(new int((*step)+1));
					} else {
						delete succesor;
					} /* if */ 
				} /* if */ 
			} else {
				delete succesor;
			} /* if */ 
		} /* while */ 
	} /* while */ 

	while(!l.EmptyP()) result->Add(l.ExtractIni());
	while(!l_step.EmptyP()) result_step->Add(l_step.ExtractIni());
} /* Generalize */ 
